package pro.softzhang.algo.lc200;

import pro.softzhang.algo.common.Utils;
import pro.softzhang.algo.common.ListNode;
import pro.softzhang.algo.flag.book.BOfferII;
import pro.softzhang.algo.flag.book.BOfferS;
import pro.softzhang.algo.flag.knowledge.KLinkedList;
import pro.softzhang.algo.flag.x.XClassic;
import pro.softzhang.algo.flag.x.XOptimal;

/**
 * 206. 反转链表
 * https://leetcode.cn/problems/reverse-linked-list
 *
 * 输入：head = [1,2,3]
 * 输出：[3,2,1]
 * TODO 练
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 */
@XClassic
@BOfferII(24)
@BOfferS
@KLinkedList
public class LC206_ReverseLinkedList {
    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, null)));
        Utils.printLinkedList(head);
        head = new Solution().reverseList(head);
        Utils.printLinkedList(head);
    }

    /**
     * 易于理解
     */
    @XOptimal
    static
    class Solution {
        /**
         * 先后再前后当下
         * @param head
         * @return
         */
        public ListNode reverseList(ListNode head) {
            // 一切围绕后续current指针展开，先存后改
            ListNode prev = null, current = head;
            while (current != null) {
                // 先保存后续指针
                ListNode next = current.next;
                current.next = prev;
                // 关键点
                prev = current;
                current = next;
            }
            return prev;
        }
    }
}